lib/Mi manual de algoritmos/version_world_finals_2009/src/grafos/ford_fulkerson_sparse.cpp

   1 /////////////// Maximum flow for sparse graphs ///////////////
   2 ///////////////    Complexity: O(V * E^2)      ///////////////
   3
   4 /*
   5   Usage:
   6   initialize_max_flow();
   7   Create graph using add_edge(u, v, c);
   8   max_flow(source, sink);
   9
  10   WARNING: The algorithm writes on the cap array. The capacity
  11   is not the same after having run the algorithm.  If you need
  12   to run the algorithm several times on the same graph, backup
  13   the cap array.
  14  */
  15
  16 const int MAXE = 50000; //Maximum number of edges
  17 const int oo = INT_MAX / 4;
  18 int cap[MAXE];
  19 int first[MAXE];
  20 int next[MAXE];
  21 int adj[MAXE];
  22 int current_edge;
  23
  24 /*
  25   Builds a directed edge (u, v) with capacity c.
  26   Note that actually two edges are added, the edge
  27   and its complementary edge for the backflow.
  28  */
  29 int add_edge(int u, int v, int c){
  30   adj[current_edge] = v;
  31   cap[current_edge] = c;
  32   next[current_edge] = first[u];
  33   first[u] = current_edge++;
  34
  35   adj[current_edge] = u;
  36   cap[current_edge] = 0;
  37   next[current_edge] = first[v];
  38   first[v] = current_edge++;
  39 }
  40
  41 void initialize_max_flow(){
  42   current_edge = 0;
  43   memset(next, -1, sizeof next);
  44   memset(first, -1, sizeof first);
  45 }
  46
  47 int q[MAXE];
  48 int incr[MAXE];
  49 int arrived_by[MAXE];
  50 //arrived_by[i] = The last edge used to reach node i
  51 int find_augmenting_path(int src, int snk){
  52   /*
  53     Make a BFS to find an augmenting path from the source to
  54     the sink.  Then pump flow through this path, and return
  55     the amount that was pumped.
  56   */
  57   memset(arrived_by, -1, sizeof arrived_by);
  58   int h = 0, t = 0;
  59   q[t++] = src;
  60   arrived_by[src] = -2;
  61   incr[src] = oo;
  62   while (h < t && arrived_by[snk] == -1){ //BFS
  63     int u = q[h++];
  64     for (int e = first[u]; e != -1; e = next[e]){
  65       int v = adj[e];
  66       if (arrived_by[v] == -1 && cap[e] > 0){
  67         arrived_by[v] = e;
  68         incr[v] = min(incr[u], cap[e]);
  69         q[t++] = v;
  70       }
  71     }
  72   }
  73
  74   if (arrived_by[snk] == -1) return 0;
  75
  76   int cur = snk;
  77   int neck = incr[snk];
  78   while (cur != src){
  79     //Remove capacity from the edge used to reach node "cur"
  80     //Add capacity to the backedge
  81     cap[arrived_by[cur]] -= neck;
  82     cap[arrived_by[cur] ^ 1] += neck;
  83     //move backwards in the path
  84     cur = adj[arrived_by[cur] ^ 1];
  85   }
  86   return neck;
  87 }
  88
  89 int max_flow(int src, int snk){
  90   int ans = 0, neck;
  91   while ((neck = find_augmenting_path(src, snk)) != 0){
  92     ans += neck;
  93   }
  94   return ans;
  95 }